﻿//90. 子集 II
//给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集
//解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    int n;
    void dfs(vector<int>& nums, int i)
    {
        if (i == n)
        {
            ans.push_back(path);
            return;
        }
        int x = nums[i];
        path.push_back(x);
        dfs(nums, i + 1);
        path.pop_back();
        //不选 x 跳过所有等于x的数 
        i++;
        while (i < n && nums[i] == x)
        {
            i++;
        }
        dfs(nums, i);
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums)
    {
        n = nums.size();
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ans;
    }
};